/*************************************************************************
	> File Name: 297.二叉树的序列化与反序列化.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 三  9/15 13:03:16 2021
 ************************************************************************/

//【思路】广搜或者深搜，此处使用深搜的先序遍历。序列化就是先序遍历，遇到空节点则记为"None"；反序列化就是将先序序列解析还原为一棵二叉树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    //深搜，先序遍历得到序列
    void rserialize(TreeNode *root, string &str) {
        if (root == nullptr) {
            str += "None,";
        } else {
            str += to_string(root->val) + ",";
            rserialize(root->left, str);
            rserialize(root->right, str);
        }
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ret;
        rserialize(root, ret);
        return ret;
    }

    //根据"None"解析先序遍历的序列得到一棵树
    TreeNode *rdeserialize(list<string> &dataArray) {
        if (dataArray.front() == "None") {
            dataArray.erase(dataArray.begin());
            return nullptr;
        }
        TreeNode *root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.begin());
        root->left = rdeserialize(dataArray);
        root->right = rdeserialize(dataArray);
        return root;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        list<string> dataArray;
        string str;
        for (auto &ch: data) {
            if (ch == ',') {
                dataArray.push_back(str);
                str.clear();
            } else {
                str.push_back(ch);
            }
        }
        if (!str.empty()) {
            dataArray.push_back(str);
            str.clear();
        }
        return rdeserialize(dataArray);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
